翻訳と辞書 Words near each other ・ Randy Baumgardner ・ Random Thoughts ・ Random Thoughts (Don Pullen album) ・ Random Thoughts (Faye Wong album) ・ Random Thoughts (Koolism album) ・ Random tree ・ Random variable ・ Random variate ・ Random vibration ・ Random Violence ・ Random Vol. 3/Sad Clown Bad Dub 7 ・ Random walk ・ Random walk closeness centrality ・ Random walk hypothesis ・ Random walk model of consumption ・ Random walker algorithm ・ Random waypoint model ・ Random White Dude Be Everywhere ・ Random wire antenna ・ Random! Cartoons ・ Random-access channel ・ Random-access machine ・ Random-access memory ・ Random-access stored-program machine ・ Random-access Turing machine ・ Random.org ・ Randomajestiq ・ Randominta ・ Randomization ・ Randomization function Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Random walker algorithm ： ウィキペディア英語版 Random walker algorithm The random walker algorithm is an algorithm for image segmentation. In the first description of the algorithm,〔L. Grady: (Random Walks for Image Segmentation ), IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 28, No. 11, pp. 1768–1783, Nov., 2006.〕 a user interactively labels a small number of pixels with known labels (called seeds), e.g., "object" and "background". The unlabeled pixels are each imagined to release a random walker, and the probability is computed that each pixel's random walker first arrives at a seed bearing each label, i.e., if a user places K seeds, each with a different label, then it is necessary to compute, for each pixel, the probability that a random walker leaving the pixel will first arrive at each seed. This computation may be determined analytically by solving a system of linear equations. After computing these probabilities for each pixel, the pixel is assigned to the label for which it is most likely to send a random walker. The image is modeled as a graph, in which each pixel corresponds to a node which is connected to neighboring pixels by edges, and the edges are weighted to reflect the similarity between the pixels. Therefore, the random walk occurs on the weighted graph (see Doyle and Snell for an introduction to random walks on graphs〔P. Doyle, J. L. Snell: Random Walks and Electric Networks, Mathematical Association of America, 1984〕). Although the initial algorithm was formulated as an interactive method for image segmentation, it has been extended to be a fully automatic algorithm, given a data fidelity term (e.g., an intensity prior).〔Leo Grady: Multilabel Random Walker Image Segmentation Using Prior Models, Proc. of CVPR, Vol. 1, pp. 763–770, 2005. ()〕 It has also been extended to other applications. The algorithm was initially published as a conference paper〔Leo Grady, Gareth Funka-Lea: Multi-Label Image Segmentation for Medical Applications Based on Graph-Theoretic Electrical Potentials, Proc. of the 8th ECCV Workshop on Computer Vision Approaches to Medical Image Analysis and Mathematical Methods in Biomedical Image Analysis, pp. 230–245, 2004.〕 and later as a journal paper.〔 ==Mathematics== Although the algorithm was described in terms of random walks, the probability that each node sends a random walker to the seeds may be calculated analytically by solving a sparse, positive-definite system of linear equations with the graph Laplacian matrix, which we may represent with the variable $L$. The algorithm was shown to apply to an arbitrary number of labels (objects), but the exposition here is in terms of two labels (for simplicity of exposition). Assume that the image is represented by a graph, with each node $v\_i$ associated with a pixel and each edge $e\_$ connecting neighboring pixels $v\_i$ and $v\_j$. The edge weights are used to encode node similarity, which may be derived from differences in image intensity, color, texture or any other meaningful features. For example, using image intensity $g\_i$ at node $v\_i$, it is common to use the edge weighting function :$w\_\; =\; \backslash exp.$ The nodes, edges and weights can then be used to construct the graph Laplacian matrix. The random walker algorithm optimizes the energy :$Q(x)\; =\; x^T\; L\; x\; =\; \backslash sum\_\; \backslash left(x\_i\; -\; x\_j\backslash right)^2$ where $x\_i$ represents a real-valued variable associated with each node in the graph and the optimization is constrained by $x\_i\; =\; 1$ for $v\_i\; \backslash in\; F$ and $x\_i\; =\; 0$ for $v\_i\; \backslash in\; B$, where $F$ and $B$ represent the sets of foreground and background seeds, respectively. If we let $S$ represent the set of nodes which are seeded (i.e., $S\; =\; F\; \backslash cup\; B$) and $\backslash overline$ represent the set of unseeded nodes (i.e., $S\; \backslash cup\; \backslash overline\; =\; V$ where $V$ is the set of all nodes), then the optimum of the energy minimization problem is given by the solution to :$$ L_} x_,S} x_, where the subscripts are used to indicate the portion of the graph Laplacian matrix $L$ indexed by the respective sets. To incorporate likelihood (unary) terms into the algorithm, it was shown in 〔 that one may optimize the energy :$Q(x)\; =\; x^T\; L\; x\; +\; \backslash gamma\; \backslash left((1-x)^T\; F\; (1-x)\; +\; x^T\; B\; x\backslash right)\; =\; \backslash sum\_\; \backslash left(x\_i\; -\; x\_j\backslash right)^2\; +\; \backslash gamma\; \backslash left(\backslash sum\_\; f\_i\; (1-x\_i)^2\; +\; \backslash sum\_\; b\_i\; x\_i^2\; \backslash right),$ for positive, diagonal matrices $F$ and $B$. Optimizing this energy leads to the system of linear equations :$$ \left(L_} + \gamma F_} + \gamma B_}\right) x_,S} x_ - \gamma F_}. The set of seeded nodes, $S$, may be empty in this case (i.e., $\backslash overline=V$), but the presence of the positive diagonal matrices allows for a unique solution to this linear system. For example, if the likelihood/unary terms are used to incorporate a color model of the object, then $f\_i$ would represent the confidence that the color at node $v\_i$ would belong to object (i.e., a larger value of $f\_i$ indicates greater confidence that $v\_i$ belonged to the object label) and $b\_i$ would represent the confidence that the color at node $v\_i$ belongs to the background. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Random walker algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.